<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // 可能并不是对的，这是自己的理解
      // 参考：
      // https://www.jianshu.com/p/f254ec665e57（最详细）
      // https://juejin.cn/post/6957919292352364551（最全面）
      // https://segmentfault.com/a/1190000017569816（有一些补充）

      // 定义节点
      function Node(data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
      }

      // 二叉查找树类
      function BST() {
        this.root = null;
        this.insert = insert;
        this.preOrder = preOrder;
        this.inOrder = inOrder;
        this.postOrder = postOrder;
        this.find = find;
        this.getMin = getMin;
        this.getMax = getMax;
        this.remove = remove;
      }

      // 插入
      function insert(data) {
        let n = new Node(data, null, null);
        // 如果根节点是空,那插入的节点就作为根节点
        if (this.root === null) {
          this.root = n;
        } else {
          let current = this.root;
          // 当前要插入结点的上一个节点
          let parent;
          while (true) {
            // 记录上一个节点的位置,如果下一个节点合适就得插入到这里
            parent = current;
            if (data < current.data) {
              current = current.left;
              // 如果当前节点的左节点不存在,就将新节点放到这个位置,右节点同理
              if (current === null) {
                parent.left = n;
                break;
              }
            } else {
              current = current.right;
              if (current === null) {
                parent.right = n;
                break;
              }
            }
          }
        }
      }

      // 查找
      function find(data) {
        let current = this.root;
        while (current) {
          if (data === current.data) {
            return current;
          } else if (data < current.data) {
            current = current.left;
          } else {
            current = current.right;
          }
        }
        return null;
      }

      // 删除
      function remove(data) {
        return removeNode(this.root, data);
      }
      // 真正的删除方法
      function removeNode(node, data) {
        if (!node) {
          return null;
        }
        if (data === node.data) {
          if (!node.left && !node.right) {
            return null;
          }
          if (!node.left) {
            return node.right;
          }
          if (!node.right) {
            return node.left;
          }
          // 这里方法就是找到被删除节点左边的最大节点或者被删除节点右边的最小节点,让这个节点替代当前删除节点的位置,
          // 然后再去删除找到的这个节点,就这样一递归,直到当前要删除的节点下面没有两个不为null的节点,然后进入上面的几种判断情况
          // let tempNode = getMinNode(node.right);
          let tempNode = getMaxNode(node.left);
          node.data = tempNode.data;
          // node.right = removeNode(node.right, tempNode.data);
          node.left = removeNode(node.left, tempNode.data);
        } else if (data < node.data) {
          node.left = removeNode(node.left, data);
        } else {
          node.right = removeNode(node.right, data);
        }
        return node;
      }
      // 查找最小值的节点
      function getMinNode(node) {
        if (!node.left) {
          return node;
        } else {
          return getMinNode(node.left);
        }
      }
      // 查找最大值的节点
      function getMaxNode(node) {
        if (!node.right) {
          return node;
        } else {
          return getMaxNode(node.right);
        }
      }

      // 先序遍历
      function preOrder(node) {
        if (node) {
          console.log(node.data);
          preOrder(node.left);
          preOrder(node.right);
        }
      }

      // 中序遍历
      function inOrder(node) {
        if (node) {
          inOrder(node.left);
          console.log(node.data);
          inOrder(node.right);
        }
      }

      // 后序遍历
      function postOrder(node) {
        if (node) {
          postOrder(node.left);
          postOrder(node.right);
          console.log(node.data);
        }
      }

      // 查找最大值
      function getMax() {
        let current = this.root;
        while (current.right) {
          current = current.right;
        }
        return current.data;
      }

      // 查找最小值
      function getMin() {
        let current = this.root;
        while (current.left) {
          current = current.left;
        }
        return current.data;
      }

      // 初始化
      let nums = new BST();

      // 调用
      nums.insert(23);
      nums.insert(45);
      nums.insert(16);
      nums.insert(37);
      nums.insert(3);
      nums.insert(99);
      nums.insert(22);

      // preOrder(nums.root);
      // console.log('---------------------------')
      // inOrder(nums.root);
      // console.log('---------------------------')
      // postOrder(nums.root);

      console.log(nums.find(45));

      // console.log(nums.getMax());
      // console.log(nums.getMin());

      // nums.remove(23);
      postOrder(nums.root);

      // 查看
      console.log(nums);
    </script>
  </body>
</html>
